/*
 *  AUdistance.cpp
 *  AUdistance
 *
 *  Created by Santi Onta√±√≥n on 9/13/06.
 *
 */


#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "assert.h"

#include "List.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"

#include "SpecialTerm.h"

#include "FT_refinement.h"
#include "FT_generalization.h"
#include "AUfeatureterm.h"

#include "entropy.h"
#include "AUdistance.h"


List<FeatureTerm> *split_into_patterns(FeatureTerm *f,Ontology *o,FTKBase *dm);


/*

Results:

*- 120 sponges using 1-NN and leave one out
Final results:
Accuracy: 93.3333%  (112 8)
Individual class results:
astrophorida  37 3
axinellida  40 0
hadromerida  35 5
Time taken: 2099259   

*- 280 sponges using 1-NN and leave one out
Accuracy: 91.4286%  (256 24)
Individual class results:
astrophorida  88 7
axinellida  62 6
hadromerida  106 11
Time taken: 9996898

*/

float AUdistance(FeatureTerm *f1,FeatureTerm *f2,Ontology *o,FTKBase *dm)
{
	FeatureTerm *au;
	int steps_au=0;
	int additional_steps_f1=0;
	int additional_steps_f2=0;
	
	List<FeatureTerm> objects;

	printf("["); fflush(0);
	// Count antiunification steps:
	{
		List<FeatureTerm> aul;
		List<int> stepsl;
		objects.Add(f1);
		objects.Add(f2);
		antiunification(&aul,&stepsl,&objects,SPECIALIZATION_LANGUAGE_L2,0,o,dm,true,AU_VERSION_FAST);
		objects.ExtractAll();
		au=aul.ExtractIni();
		steps_au=*(stepsl[0]);
	}
	
	printf("a = %i, ",steps_au); fflush(0);
	// Count additional f1 steps:		
	{
		List<int> stepsl;
		List<FeatureTerm> aul;
		List<FeatureTerm> startl;
		objects.Add(f1);
		startl.Add(au);
		antiunification(&aul,&stepsl,&objects,SPECIALIZATION_LANGUAGE_L2,&startl,o,dm,true,AU_VERSION_FAST);
		objects.ExtractAll();
		startl.ExtractAll();
		additional_steps_f1=*(stepsl[0]);

	}

	
	printf("b = %i, ",additional_steps_f1); fflush(0);
	// Count additional f2 steps:
	{
		List<int> stepsl;
		List<FeatureTerm> aul;
		List<FeatureTerm> startl;
		objects.Add(f2);
		startl.Add(au);
		antiunification(&aul,&stepsl,&objects,SPECIALIZATION_LANGUAGE_L2,&startl,o,dm,true,AU_VERSION_FAST);
		objects.ExtractAll();
		startl.ExtractAll();
		additional_steps_f2=*(stepsl[0]);
	}
	
	delete au;
	
	printf("c = %i] ",additional_steps_f2); fflush(0);

	return 1.0f-(float(steps_au*2)/float(steps_au*2+additional_steps_f1+additional_steps_f2));
} /* AUdistance */ 



// Properties distance 1:
/*
	- Take the leaves of f1, and the leaves of f2 as patterns (line in unification-LID)
	- find the amount of patterns that subsume both
*/ 

/*
	
*- 120 sponges using 1-NN and leave one out
Accuracy: 93.3333%  (112 8)
Individual class results:
astrophorida  36 4
axinellida  40 0
hadromerida  36 4
Time taken: 10847

*- 120 sponges using 3-NN and leave one out
Accuracy: 95.8333%  (115 5)
Individual class results:
astrophorida  40 0
axinellida  39 1
hadromerida  36 4
Time taken: 9550

*- 120 sponges using 5-NN and leave one out
Accuracy: 94.1667%  (113 7)
Individual class results:
astrophorida  40 0
axinellida  39 1
hadromerida  34 6
Time taken: 9625

*- 120 sponges using 7-NN and leave one out
Accuracy: 92.5%  (111 9)
Individual class results:
astrophorida  39 1
axinellida  39 1
hadromerida  33 7
Time taken: 9763

*- 280 sponges using 1-NN and leave one out
Accuracy: 93.5714%  (262 18)
Individual class results:
astrophorida  87 8
axinellida  61 7
hadromerida  114 4
Time taken: 51478

*- 280 sponges using 3-NN and leave one out
Accuracy: 92.8571%  (260 20)
Individual class results:
astrophorida  90 5
axinellida  58 10
hadromerida  112 5
Time taken: 42737

*- 280 sponges using 5-NN and leave one out
Accuracy: 90.7143%  (254 26)
Individual class results:
astrophorida  88 7
axinellida  57 11
hadromerida  109 8
Time taken: 42952

*- 280 sponges using 7-NN and leave one out
Accuracy: 89.2857%  (250 30)
Individual class results:
astrophorida  90 5
axinellida  56 12
hadromerida  104 13
Time taken: 42575

*- 503 sponges using 1-NN and leave one out
Accuracy: 86.8787%  (437 66)
Individual class results:
astrophorida  88 7
halichondrida  24 12
axinellida  57 11
hadromerida  103 14
poecilosclerida  77 18
haplosclerida  38 4
dictyoceratida  50 0
Time taken: 121747

*- 503 sponges using 3-NN and leave one out
Accuracy: 86.6799%  (436 67)
Individual class results:
astrophorida  88 7
halichondrida  20 16
axinellida  55 13
hadromerida  105 12
poecilosclerida  79 16
haplosclerida  39 3
dictyoceratida  50 0
Time taken: 121162

*/

List<FeatureTerm> leaf_patterns_cache_descriptions;
List< List<FeatureTerm> > leaf_patterns_cache_patterns;

void AUdistance_leaf_patterns_clear_cache(void)
{
	leaf_patterns_cache_descriptions.Delete();
	leaf_patterns_cache_patterns.Delete();
} /* AUdistance_leaf_patterns_clear_cache */ 


float AUdistance_leaf_patterns(FeatureTerm *f1,FeatureTerm *f2,Ontology *o,FTKBase *dm)
{
	int common=0,total=0;
	List<FeatureTerm> *f1_patterns,*f2_patterns;
	FeatureTerm *pattern;
	
	{
		int pos;
		pos=leaf_patterns_cache_descriptions.Position(f1);
		if (pos==-1) {
			f1_patterns=split_into_patterns(f1,o,dm);
			leaf_patterns_cache_descriptions.Add(new FeatureTerm(f1));
			leaf_patterns_cache_patterns.Add(f1_patterns);
//			printf("*");
		} else {
			f1_patterns=leaf_patterns_cache_patterns[pos];
		} // if
	}

	{
		int pos;
		pos=leaf_patterns_cache_descriptions.Position(f2);
		if (pos==-1) {
			f2_patterns=split_into_patterns(f2,o,dm);
			leaf_patterns_cache_descriptions.Add(new FeatureTerm(f2));
			leaf_patterns_cache_patterns.Add(f2_patterns);
//			printf("*");
		} else {
			f2_patterns=leaf_patterns_cache_patterns[pos];
		} // if
	}

	total=f1_patterns->Length()+f2_patterns->Length();
	
	f1_patterns->Rewind();
	while(f1_patterns->Iterate(pattern)) if (pattern->subsumes(f2)) common++;
	f2_patterns->Rewind();
	while(f2_patterns->Iterate(pattern)) if (pattern->subsumes(f1)) common++;
	
//	printf("[ %i / %i ] ",common,total);

	return 1.0f-(float(common)/float(total));
} /* AUdistance_leaf_patterns */ 



// Properties distance 2:
/*
	- The same, but filtering duplicates (How much does this improve?)
*/

/*
	
*- 280 sponges using 1-NN and leave one out
Accuracy: 93.9286%  (263 17)
Individual class results:
astrophorida  88 7
axinellida  61 7
hadromerida  114 3
Time taken: 153530

*- 280 sponges using 3-NN and leave one out
Accuracy: 92.5%  (259 21)
Individual class results:
astrophorida  90 5
axinellida  58 10
hadromerida  111 6
Time taken: 154863

*- 280 sponges using 5-NN and leave one out
Accuracy: 90.7143%  (254 26)
Individual class results:
astrophorida  91 4
axinellida  55 13
hadromerida  108 9
Time taken: 153189

*- 503 sponges using 1-NN and leave one out
Accuracy: 86.6799%  (436 67)
Individual class results:
astrophorida  87 8
halichondrida  24 12
axinellida  57 11
hadromerida  102 15
poecilosclerida  79 16
haplosclerida  37 5
dictyoceratida  50 0
Time taken: 562029


*- 503 sponges using 3-NN and leave one out
Accuracy: 86.4811%  (435 68)
Individual class results:
astrophorida  87 8
halichondrida  19 17
axinellida  56 12
hadromerida  104 13
poecilosclerida  80 15
haplosclerida  39 3
dictyoceratida  50 0
Time taken: 561878

*/ 
float AUdistance_leaf_patterns2(FeatureTerm *f1,FeatureTerm *f2,Ontology *o,FTKBase *dm)
{
	int common=0,total=0;
	List<FeatureTerm> *f1_patterns,*f2_patterns;
	FeatureTerm *pattern;
	List<FeatureTerm> filtered_f2_patterns;
	
	{
		int pos;
		pos=leaf_patterns_cache_descriptions.Position(f1);
		if (pos==-1) {
			f1_patterns=split_into_patterns(f1,o,dm);
			leaf_patterns_cache_descriptions.Add(new FeatureTerm(f1));
			leaf_patterns_cache_patterns.Add(f1_patterns);
//			printf("*");
		} else {
			f1_patterns=leaf_patterns_cache_patterns[pos];
		} // if
	}

	{
		int pos;
		pos=leaf_patterns_cache_descriptions.Position(f2);
		if (pos==-1) {
			f2_patterns=split_into_patterns(f2,o,dm);
			leaf_patterns_cache_descriptions.Add(new FeatureTerm(f2));
			leaf_patterns_cache_patterns.Add(f2_patterns);
//			printf("*");
		} else {
			f2_patterns=leaf_patterns_cache_patterns[pos];
		} // if
	}
	
	// Filter duplicates:
	{
		List<FeatureTerm> l1,l2;
		FeatureTerm *pattern2;
		bool found;
		l1.Instance(*f1_patterns);
		l2.Instance(*f2_patterns);
		l2.Rewind();
		while(l2.Iterate(pattern2)) {
			found=false;
			l1.Rewind();
			while(l1.Iterate(pattern) && !found) {
				if (pattern->equivalents(pattern2)) {
					found=true;
				} // if
			} // while
			if (!found) filtered_f2_patterns.Add(pattern2);
		} // while 
	}

	total=f1_patterns->Length()+filtered_f2_patterns.Length();
	
	f1_patterns->Rewind();
	while(f1_patterns->Iterate(pattern)) if (pattern->subsumes(f2)) common++;
	filtered_f2_patterns.Rewind();
	while(filtered_f2_patterns.Iterate(pattern)) if (pattern->subsumes(f1)) common++;
	
	filtered_f2_patterns.ExtractAll();
	
//	printf("[ %i / %i ] ",common,total);

	return 1.0f-(float(common)/float(total));
} /* AUdistance_leaf_patterns2 */ 



// Properties distance 2W:
/*
	- Like 2, but using weights for the properties
*/

/*

*- 120 sponges using 1-NN and leave one out
Accuracy: 95%  (114 6)
Individual class results:
astrophorida  37 3
axinellida  39 1
hadromerida  38 2
Time taken: 743708

*- 120 sponges using 3-NN and leave one out
Accuracy: 96.6667%  (116 4)
Individual class results:
astrophorida  40 0
axinellida  39 1
hadromerida  37 3
Time taken: 681070

*/

float AUdistance_leaf_patterns2w(FeatureTerm *f1,FeatureTerm *f2,List<FeatureTerm> *descriptions,List<FeatureTerm> *solutions,Ontology *o,FTKBase *dm)
{
	float common=0,total=0;
	List<FeatureTerm> *f1_patterns,*f2_patterns;
	List<float> *f1_patterns_weight,*f2_patterns_weight;
	FeatureTerm *pattern;
	List<FeatureTerm> filtered_f2_patterns;
	float *fp;
	
	{
		int pos;
		pos=leaf_patterns_cache_descriptions.Position(f1);
		if (pos==-1) {
			f1_patterns=split_into_patterns(f1,o,dm);
			leaf_patterns_cache_descriptions.Add(new FeatureTerm(f1));
			leaf_patterns_cache_patterns.Add(f1_patterns);
//			printf("*");
		} else {
			f1_patterns=leaf_patterns_cache_patterns[pos];
		} // if
	}

	{
		int pos;
		pos=leaf_patterns_cache_descriptions.Position(f2);
		if (pos==-1) {
			f2_patterns=split_into_patterns(f2,o,dm);
			leaf_patterns_cache_descriptions.Add(new FeatureTerm(f2));
			leaf_patterns_cache_patterns.Add(f2_patterns);
//			printf("*");
		} else {
			f2_patterns=leaf_patterns_cache_patterns[pos];
		} // if
	}
	
	// Filter duplicates:
	{
		List<FeatureTerm> l1,l2;
		FeatureTerm *pattern2;
		bool found;
		l1.Instance(*f1_patterns);
		l2.Instance(*f2_patterns);
		l2.Rewind();
		while(l2.Iterate(pattern2)) {
			found=false;
			l1.Rewind();
			while(l1.Iterate(pattern) && !found) {
				if (pattern->equivalents(pattern2)) {
					found=true;
				} // if
			} // while
			if (!found) filtered_f2_patterns.Add(pattern2);
		} // while 
	}
	
	// Compute the weights for each property:
	{
		List<FeatureTerm> different_solutions;
		float w;
		int coverage;
		
		f1_patterns_weight=new List<float>;
		f2_patterns_weight=new List<float>;

		// Compute the list of different solutions:
		{
			FeatureTerm *sol;
	
			solutions->Rewind();
			while(solutions->Iterate(sol)) {
				if (!different_solutions.MemberP(sol)) different_solutions.Add(new FeatureTerm(sol));
			} /* while */ 
		}
		
		f1_patterns->Rewind();
		while(f1_patterns->Iterate(pattern)) {
			w=1-h_rldm(descriptions,solutions,&different_solutions,pattern,&coverage);
//			w=compute_pattern_weight(pattern,descriptions,solutions);
			f1_patterns_weight->Add(new float(w));
		} // while 
		filtered_f2_patterns.Rewind();
		while(filtered_f2_patterns.Iterate(pattern)) {
			w=1-h_rldm(descriptions,solutions,&different_solutions,pattern,&coverage);
//			w=compute_pattern_weight(pattern,descriptions,solutions);
			f2_patterns_weight->Add(new float(w));
		} // while 
	}

	total=0;
	
	f1_patterns->Rewind();
	f1_patterns_weight->Rewind();
	while(f1_patterns->Iterate(pattern) && f1_patterns_weight->Iterate(fp)) {
		total+=*fp;
		if (pattern->subsumes(f2)) common+=*fp;
	} // while
	filtered_f2_patterns.Rewind();
	f2_patterns_weight->Rewind();
	while(filtered_f2_patterns.Iterate(pattern) && f2_patterns_weight->Iterate(fp)) {
		total+=*fp;
		if (pattern->subsumes(f1)) common+=*fp;
	} // while 
	
	filtered_f2_patterns.ExtractAll();
	delete f1_patterns_weight;
	delete f2_patterns_weight;
	
//	printf("[ %f / %f ] ",common,total);

	return 1.0f-(common/total);
} /* AUdistance_leaf_patterns2w */ 



// Properties distance 3:
/*
	- Considering ALL the paths in the feature term, not only the leaves
*/

// Properties distance 4 (How equivalent this is to the AU distance?):
/*
	- Find the set of properties of f1 and the set of properties of f2
	- filter for duplicates
	- find the amount of properties that both satisfy
*/ 






List<FeatureTerm> *split_into_patterns(FeatureTerm *f,Ontology *o,FTKBase *dm)
{
	List<FeatureTerm> *patterns=new List<FeatureTerm>;
	
	// compute all paths (objects containing a single path with the final value):
	{
		List<Path> paths;
		List< List<FeatureTerm> > values;

		List< List<FeatureTerm> > stack_values;
		List<Path> stack_path;
		List<Symbol> *l;
		List<FeatureTerm> *l2;
		FeatureTerm *ft,*ft2,*ft3;
		Symbol *feature;
		Path *path,*path2;
		List<FeatureTerm> *value,*value2;
		int max_depth=4;

		value=new List<FeatureTerm>;
		value->Add(new FeatureTerm(f));
		stack_values.Add(value);
		stack_path.Add(new Path);

		/* get all paths: */ 
		while(!stack_values.EmptyP()) {
			value=stack_values.ExtractIni();
			path=stack_path.ExtractIni();

			value->Forward();
			ft=value->GetObj();

			if (path->Length()>=max_depth || ft->leafP()) {
				value2=new List<FeatureTerm> (*value);
				ft2=value2->ExtractIni();
				delete ft2;
				values.Add(value2);
				paths.Add(new Path(*path));
			} else {

				if (ft->isFeatureTerm()) {
					l=ft->getSort()->getFeatures();

					while(!l->EmptyP()) {
						feature=l->ExtractIni();

						ft2=ft->featureValue(feature);
						if (ft2!=0) {
							path2=new Path(*path);
							path2->Add(new Symbol(feature));
							value2=new List<FeatureTerm>(*value);
							value2->Add(ft2);
							stack_values.Add(value2);
							stack_path.Add(path2);
						} /* if */ 

						delete feature;
					} /* while */ 
					delete l;

				} /* if */ 

				if (ft->isSet()) {
					l2=ft->set_values();

					while(!l2->EmptyP()) {
						ft2=l2->ExtractIni();

						path2=new Path(*path);
						value2=new List<FeatureTerm>(*value);
						ft3=value2->Extract();
						delete ft3;
						value2->Add(ft2);
						stack_values.Add(value2);
						stack_path.Add(path2);
					} /* while */ 
					delete l2;
				} /* if */ 

			} /* if */ 

			delete value;
			delete path;
		} /* while */ 

		/* construct the patterns representing the paths: */ 
		{
			Sort *sort;
			Symbol *feature;
			FeatureTerm *pattern,*pointer,*ft,*ft2;

			paths.Rewind();
			values.Rewind();
			while(paths.Iterate(path) && values.Iterate(value)) {
				path->Rewind();
				value->Rewind();

				sort=f->getSort();
				pattern=new FeatureTerm((Symbol *)0,sort,0);
				pointer=pattern;

				while(path->Iterate(feature) &&
					  value->Iterate(ft)) {

					if (path->EndP()) {
						pointer->defineFeatureValue(feature,new FeatureTerm(ft));
						pointer=0;
					} else {
						sort=ft->getSort();
						ft2=new FeatureTerm((Symbol *)0,sort,0);
						pointer->defineFeatureValue(feature,ft2);
						pointer=ft2;
					} /* if */ 
					
				} /* while */ 

				patterns->Add(pattern);
			} /* while */ 
		}
	}
		
	return patterns;
} /* split_into_patterns */ 





